package com.sise.Backtracking;

/**
 *      79. 单词搜索
 *      _offer_12_exist(同一道题)
 *
 *      给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *      单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 */
public class _79_exist {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {                // 这里使用双层 for 循环，因为每一个点都可能作为 起点，然后再使用 dfs()
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, word, i, j, 0)) return true;     // 只要有一个 dfs 返回 true，那么就说明存在这个值
            }
        }
        return false;                                           // 如果所有的 dfs 都不存在，那么就返回 false
    }

    private boolean dfs(char[][] board, String word, int i, int j, int num) {       // 这里利用的是 num++ 控制匹配的字符是否相等
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || word.charAt(num) != board[i][j]) {   // 判断边界条件 && 当前数值是否匹配
            return false;
        }

        if (num == word.length() - 1) return true;

        board[i][j] = '\0';                                 // 为了防止重复访问，设置状态值。例如 ABA 可能会回头访问，那么就设置为 \0 BA
        boolean res = dfs(board, word, i + 1, j, num + 1)   // 这里要注意 num+1，如果是 num++，那么 dfs 中的 num 还是原来的值
                || dfs(board, word, i - 1, j, num + 1)
                || dfs(board, word, i, j + 1, num + 1)
                || dfs(board, word, i, j - 1, num + 1);
        board[i][j] = word.charAt(num);                     // 状态重置
        return res;
    }
}